import java.util.Arrays;
import java.util.Comparator;

public class PriorityQueue<I extends Number> {
    public int[] elem;
    public int usedSize;

    public PriorityQueue() {
        this.elem=new int[10];
    }

    /**
     * 建堆的时间复杂度：
     *
     * @param array
     */
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            usedSize++;
        }
    }
    public void createHeap() {
        //parent的下标：(i-1)/2  i=len-1
        for(int parent=(usedSize-1-1)/2;parent>=0;parent--) {
            shiftDown(parent,usedSize);
        }
    }


    /**
     *
     * @param parent 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int parent,int len) {
       int child=2*parent+1;

       //至少有左孩子
       while (child<len) {
           //左右孩子比较大小
           if(child+1<len&&elem[child]<elem[child+1]) { //不可交换条件位置，防止越界
               child=child+1;
           }//if语句保证此时child保存左右孩子最大值的下标
           if(elem[child]>elem[parent]) {
               swapij(child,parent);
               //为什么不能写swap(elem[child],elem[parent]);
               //swap(elem[child],elem[parent]);
               parent=child;
               child=2*parent+1;
           }else {
               break;
           }
       }
    }

    private void swap(int a,int b) {
        int tmp=a;
        a=b;
        b=tmp;
    }
    private void swapij(int i,int j) {
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }
    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()) {
           elem=Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize]=val;
        shiftUp(usedSize);
        usedSize++;
    }

    private void shiftUp(int child) {
        int parent=(child-1)/2;
        while (child>0) {
            if (elem[child] > elem[parent]) {
                swapij(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        return elem.length==usedSize;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public int pop() {
        //判空
        if(isEmpty()) {
            return -1;
        }
        int oldVal=elem[0];
        swapij(0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return oldVal;
    }

    public boolean isEmpty() {
        return usedSize==0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        return elem[0];
    }

    //topk问题：最小的前k个数据 小根堆
    public int[] topMinK(int[] array,int k) {
        //topk问题：最小的前k个数据 小根堆
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();

        //建立小根堆 O(n*logn)
        for (int i=0;i<array.length;i++) {
            priorityQueue.push(array[i]);
        }

        //k*logn
        int[] ret=new int[k];

        for (int i=0;i<k;i++) {
            ret[i]=priorityQueue.pop();
        }

        return ret;
    }

    class Imp implements Comparator<Integer> {

        public int compare(Integer o1,Integer o2) {
            return o2.compareTo(o1);  //大根堆
        }

    }


    //topk问题：最小的前k个数据 大根堆（优解）
    public int[] smalleastKa(int[] array,int k) {
        //建立大根堆
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Imp());

        for (int i = 0; i < k; i++) {
            priorityQueue.push(array[i]);
        }

        for (int i = k; i < array.length; i++) {
            int top=priorityQueue.peekHeap();
            if(array[i]<top) {
                priorityQueue.pop();
                priorityQueue.push(array[i]);
            }
        }

        int[] ret=new int[k];
        for (int i = 0; i < array.length; i++) {
            ret[i]=priorityQueue.pop();
        }
        return ret;
    }

    //堆排序（大根堆）
    public void heapSort() {
        int end=usedSize-1;
        while (end>0) {
            swapij(0,end);
            shiftDown(0,end);
            end--;
        }
    }


}